package LiKouBrushQuestions;

import org.w3c.dom.Node;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * @author 23737
 * 2021.9.2
 */
public class JianZhiOffer_two_three {
    public static void main(String[] args) {

    }
}

//输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
class ReverseLinkedListByArray {
    public int[] reversePrint(ListNode head) {
        Stack<ListNode> stack = new Stack<>();
        ListNode temp = head;
        while (temp != null) {
            stack.push(temp);
            temp = temp.next;
        }
        int size = stack.size();
        int[] Reverse = new int[size];
        for (int i = 0; i < size; i++) {
            Reverse[i] = stack.pop().val;
        }
        return Reverse;
    }
}

//定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
//使用迭代法进行求解
class ReverseLinkedList {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null, cur=head;
        while (cur != null) {
            ListNode next;
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

//请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点
// 还有一个 random 指针指向链表中的任意节点或者 null。
class NodeCopyLinkedList {
    int val;
    Node next;
    Node random;

    public NodeCopyLinkedList(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
class CopyLinkedList{
    public NodeCopyLinkedList copyRandomList(NodeCopyLinkedList head) {
        if (head == null) {
            return head;
        }
        Map<NodeCopyLinkedList, NodeCopyLinkedList> map = new HashMap<>();
        for (NodeCopyLinkedList cur = head; cur != null; cur = (NodeCopyLinkedList) cur.next) {
            map.put(cur, new NodeCopyLinkedList(cur.val));
        }
        for (NodeCopyLinkedList cur = head; cur != null; cur = (NodeCopyLinkedList) cur.next) {
            map.get(cur).next = (Node) map.get(cur.next);
            map.get(cur).random = (Node) map.get(cur.random);
        }
        return map.get(head);
    }
}

